1. Technical Field
The present invention relates to a semiconductor device for implementing a cryptographic algorithm. In particular, the present invention relates to a tamper-resistant integrated memory circuit equipped with a countermeasure against attacks for exploiting secret information (mainly cryptographic keys) processed by a semiconductor device, by using side channel information such as power consumption of the semiconductor device or radiated electromagnetic waves dependent on the power consumption. The present invention also relates to a cryptographic circuit using the tamper-resistant integrated memory circuit.
2. Background Art
In recent years, a system (e.g., an IC card) for storing financial information or personal information by using an LSI has become widely popular, and the importance of ensuring the reliability and security of such a security LSI is significantly increasing. In the security LSI, confidential information is protected by using a cryptographic circuit included therein; thus, leakage of information of the cryptographic key must be prevented. Modern cryptographic algorithm such as 3DES (Triple Data Encryption Standard) or AES (Advanced Encryption Standard) ensures high security in which a cryptographic key cannot be identified within a realistic time even by using the fastest computer with a pair of plaintext and ciphertext (input and output).
As another method for exploiting a cryptographic key, a method in which a cryptographic key is identified by using side channel information such as power consumption of a semiconductor device during execution of a cryptographic algorithm or radiated electromagnetic waves dependent on the power consumption can be a threat. As one of such side channel attacks, P. Kocher reported the “differential power attack” (DPA: differential power analysis) in 1999. The attack is disclosed in Non-patent Literature 1 (Paul Kocher, Joshua Jaffe, and Benjamin Jun, “Differential Power Analysis”, Advances in Cryptography-Proceedings of CRYPTO '99, Springer-Verlag, August 1999, pp. 388-397) below and is so far considered to be the most powerful attack. This method relies on the fact that there is a correlation between a signal value or signal transition probability and power consumption during operation of a cryptographic device. This theory is specifically described below using a 2-input AND gate shown in FIG. 1(a). Assuming that the inputs of the 2-input AND gate are written as A1 and B1 before the transition, and as A2 and B2 after the transition, the transition of the inputs has 16 combinations as shown in FIG. 1(b). Assuming that the state of the input (A1) of the terminal A before the transition denotes confidential information (indicated as “target bit”) and that the terminal B randomly changes, the output transition probability is 2/8=¼ when A1=0 (see the upper 8 rows in FIG. 1(b)), whereas the output transition probability is 4/8=½ when A1=1 (see the lower 8 rows in FIG. 1(b)). The shaded portions in FIG. 1(b) indicate cases of output transitions. As such, there is a correlation between the input of the terminal A before the transition, namely, data of A1, and power consumption. In the cryptographic device, cryptographic key data, which is confidential information, is transmitted as an electric signal within the device; thus, the cryptographic key as confidential information can be identified by statistically analyzing power consumption during operation of the cryptographic device. Although the above example describes the AND gate, the same DPA attack is possible on an OR gate, NAND, or NOR gate insofar as the gate is a nonlinear gate.
As a countermeasure against such a DPA attack, a method that eliminates the correlation between an electric signal value of the cryptographic device and cryptographic information was first proposed. Then, another method that causes the device to consume constant power regardless of the signal value of the cryptographic device was proposed.
As an example of the first of the two countermeasure methods above, Patent Literature 1 (Japanese Unexamined Patent Publication No. 2000-066585) discloses a method based on a common key block encryption DES. In the method, an input value of a substitution table that is called an S-box used for the algorithm is changed by using a random-number parameter R under certain rules. In this method, in order to obtain the same output operation result as in a normal algorithm despite the input change, operations are performed using a different S-box substitution table for each rule. Since different S-box operations are performed depending on the random number R, power consumption is varied even with the same input value and the same cryptographic key. Thus, the method prevents leakage of a correlation between a cryptographic key and power consumption. Patent Literature 2 (Japanese Unexamined Patent Publication No. 2002-519722) also discloses a similar countermeasure. This method is the same as the method in Patent Literature 1 in that another table different from the normal S-box substitution table is prepared using a random-number parameter R before the operation. These cryptographic operations disclosed in Patent Literatures 1 and 2 are generally performed by software using hardware composed of a CPU (central processing unit) and a memory accessible from the CPU, and have a drawback in that the cryptographic operation takes long compared with the later-described method using dedicated cryptographic hardware. Thus, the processing is slow in these methods.
Patent Literature 3 (International Publication WO 2006-006199) discloses an example of the second of the two countermeasure methods above. As shown in the configuration example of an S-box for DES encryption in FIGS. 12 and 13 of Patent Literature 3, an S-box table for common key encryption can be implemented by using a combinatorial logic circuit that uses negative logic and a nonlinear gate, such as an AND gate or an OR gate.
The nonlinear gate has a feature such that the output transition probability differs depending on the input data value, as described above; thus, power consumption proportional to the output transition probability also depends on the input data value. In the example of the 2-input AND gate shown in FIG. 1, the output transition probability is ¼ when the input A is 0, and the output transition probability is ½ when the input A is 1. Thus, when the input A is fixed and the input B is randomly changed, it is possible to infer whether the input A is 1 or 0 by measuring power consumption. Therefore, when bit information related to confidential information is supplied to A, it is possible to infer the value according to the power consumption.
As a countermeasure for such equalized power consumption within the nonlinear gate, Non-patent Literature 2 (K. Tiri and Ingrid Verbauwhede, “A Logic Level Design Methodology for a Secure DPA Resistant ASIC or FPGA Implementation”, Design Automation and Test in Europe Conference, pp. 246-251 (2004)) discloses a dual-rail complementary logic with precharge, which uses complementary performance gates as shown in FIG. 2(a). In this method, dual complementary signals are used as the signal to be transmitted across the logic gates. Insofar as the output nodes (to logic 0) are initialized prior to the logic operation, either of the complementary signals undergoes transition during the operation, and the transition probability of the signal line becomes constant in any operation. In a transition table shown in FIG. 2(b), the lowermost row represents initialization (/prch=0, namely, prch=1) where outputs Z and /Z are 0. The figure shows that either of the outputs Z and /Z necessarily undergoes transition after the input transition regardless of the input pattern.
However, in order to ensure constant power consumption, it is necessary to completely equalize parasitic capacitance of signal lines for transmitting the complementary signals, such as A and /A or Z and /Z. However, such equalization is not only considerably difficult in terms of LSI layout design, but also causes a practical issue since the implementation area is more than tripled by increasing the number of gates and wiring.
In contrast, the “RSL (random switching logic) gate” disclosed in Patent Literature 3 achieves equalization of power consumption by using a single-wire method in which the transition probability of the gate is equalized by a random number. FIG. 3(a) shows a NAND gate using the RSL method disclosed in Patent Literature 3. As shown in FIG. 3(b), the circuit shown in FIG. 3(a) serves as a NAND gate when a random number r is 0, and serves as a NOR gate when the random number r is 1. Prior to the operation, a /en signal is set to 1, an output z is set to 0, and precharge is performed in a similar manner to that of the aforementioned dual-rail complementary logic. Since the output transition probability of the NAND gate from the precharge state is 25%, and the output transition probability of the NOR gate from the precharge state is 75%, if the random number r changes between 1 and 0 with a probability of 50%, an output node changes with a probability of 50%. As such, the device consumes constant power regardless of the signal value of the cryptographic device. Thus, the system serves as a countermeasure against DPA. However, the system has a problem in that the desired operation result cannot be obtained. In view of this problem, as shown in FIG. 4, an EXOR operation is performed at preceding and following stages of the target combinatorial logic circuit by using the same random number r as that for the RSL method, thereby switching positive logic and negative logic in the combinatorial logic circuit; thus, the desired operation can be performed. The EXOR operation section is a linear circuit having a transition probability of 50%, which is immune to DPA attacks.
In order to obtain perfect resistance to DPA attacks, it is necessary to ensure that the logic circuit is completely hazard-free (hazard: an temporal change in signal value due to delay caused by wiring or logic elements). Therefore, the /en terminal must change from 1 to 0 after the input values of the input signals x and y are determined (see FIG. 5(a); the circuit in FIG. 5(a) is the same as in FIG. 3(a)). In addition, such transition of the /en terminal from 0 to 1 must be executed before the reception of the reset (to 0) data from the previous stage. Thus, implementation and control of an asynchronous signal circuit shown in FIG. 5(b) (denoted as the broken-line region) is required. In FIG. 5(b), TG represents a timing generator, and TC represents a timing controller. In an LSI, the driving capability of a transistor greatly changes depending on the power-supply voltage and the environmental temperature. Thus, it is difficult to equip an LSI with an asynchronous signal circuit capable of accurate timing control.
As a solution for the above problem, Non-patent Literature 3 (Yoshinobu Toyoda, Kenta Kido, Yoshiaki Shitabayashi, and Takeshi Fujino, “Proposal of domino-RSL circuit resistant to differential power analysis attack on cryptographic circuit”, technical report VLD2007-77 of the Institute of Electronics, Information and Communication Engineers) discloses a domino-RSL method. FIG. 6(a) shows a domino-RSL AND/OR gate. In this method, switching between the AND gate and the OR gate is performed by using a random number r as with the RSL method (see FIG. 6(b)); thus, this method is also resistant to DPA. In addition, since this method uses a domino logic in which an output Z becomes 0 when inputs X and Y are 0, the output value changes only once and essentially no hazard occurs. Therefore, this method has a feature in that it is not necessary to control asynchronous timing of /en signals, which is difficult to implement in the RSL method. Another feature is that the method requires a fewer transistors, and therefore the implementation area per gate is smaller than with an RSL circuit. Non-patent Literature 4 (Kazuki Okuyama, Kenji Kojima, Katsuhiko Iwai, and Takeshi Fujino, “Verification of DPA resistance for cipher implementation using Domino-RSL on FPGA”, the Symposium on Cryptography and Information Security (SCIS2010), January 2010) discloses DPA resistance of a DES cryptographic circuit using this domino-RSL circuit.
FIG. 7 shows a circuit block diagram of a DES cryptographic circuit using the domino-RSL method. In the circuit, the domino-RSL method is applied only to an S-box circuit that requires a nonlinear gate. The S-box circuit in the DES cryptographic circuit uses 8 kinds of tables each having 6 inputs and 4 outputs. Accordingly, the figure shows 8 kinds of S-boxes (S-box 1 to S-box 8). In each S-box, a table having 6 inputs and 4 outputs is described in a hardware description language and can be converted into a netlist including a domino-RSL gate, by using a logic synthesis tool (the SIS logic synthesis tool distributed by UC Berkley) capable of creating logic with no negative logic. In the figure, each EXOR gate RT in the circuit serves to carry out a random mask method against hamming-distance-type DPA attacks using DFF transition.